import java.util.*;

public class 最小的K个数 {
    /*
    https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=295&tqId=23263&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page@
    最小的k个数, 用堆是最简单的
    但是我们选择使用快速选择算法

    附一道练习题,
    https://leetcode.cn/problems/kth-largest-element-in-an-array/
     */
    public static void swap(int[] nums,int a,int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //边界处理
        if(k == 0){
            return list;
        }
        //当找到这个数的时候, 此时这个数前面的排序已经完成了
        quickSort(input,0,input.length - 1, k);
        for(int i = 0;i < k;i++){
            list.add(input[i]);
        }
        return list;
    }

    private void quickSort(int[] arr,int left,int right,int k){
        //找出基准元素
        int key = arr[new Random().nextInt(right - left + 1)  + left];
        //[left,l]属于小于key [l + 1,r - 1]属于等于key  [r,right]属于大于key
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r){
            if(arr[i] < key){
                swap(arr,++l,i++);
            }else if(arr[i] == key){
                i++;
            }else{
                swap(arr,--r,i);
            }
        }
        //b是中间的元素的个数, a是左边元素的个数
        int b = r - l - 1;
        int a = l - left + 1;
        //如果k小于等于a, 说明k范围内的没有排序, 继续边找边排序
        if(a >= k){
            quickSort(arr,left,l,k);
        //如果刚好落在, 等于的那边, 前面不要求顺序, 直接返回即可
        }else if(b + a >= k){
            return;
        }else{
            //如果不在这两个范围, 因为范围从r开始, 所以要减去前两个元素的个数
            quickSort(arr,r,right,k - a - b);
        }
    }

}
